#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time    : 2020/6/5 上午9:53
# @Author  : fugang_le
# @Software: PyCharm

# 冒泡排序
def bubble_sort(arr):
    for i in range(1, len(arr)):
        flag = True
        for j in range(0, len(arr) - i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = False
        if flag:
            break
    return arr


# 选择排序
def selection_sort(arr):
    for i in range(len(arr)-1):
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        if i != min_index:
            arr[i], arr[min_index] = arr[min_index], arr[i]
        return arr


# 插入排序
def insertion_sort(arr):
    for i in range(len(arr)):
        pre_index = i - 1
        current = arr[i]
        while pre_index >=0 and arr[pre_index] > current:
            arr[pre_index+1] = arr[pre_index]
            pre_index -= 1
        arr[pre_index] = current
    return arr


# 希尔排序
def shell_sort(arr):
    gap = round(len(arr) / 2)
    while gap >= 1:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i
            while j - gap >= 0 and arr[j-gap] > temp:
                arr[j] = arr[j-gap]
                j -= gap
            arr[j] = temp
        gap = round(gap / 2)



# 归并排序
def merge_sort(ary):
    def merge(left, right):
        res = []
        i=j=k=0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                res.append(left[i])
                i += 1
            else:
                res.append(right[j])
                j += 1
        res = res + left[i:] + right[j:]
        return res

    if len(ary) <= 1:
        return ary

    media = int(len(ary)/2)
    left = merge_sort(ary[:media])
    right = merge_sort(ary[media:])
    return merge(left, right)

def quick_sort(ary):
    return qsort(ary, 0, len(ary)-1)

def qsort(ary, start, end):
    if start < end:
        left = start
        right = end
        key = ary[start]
    else:
        return ary

    while left < right:
        while left < right and ary[right] >= key:
            right -= 1
        if left < right:
            ary[left] = ary[right]
            left += 1
        while left < right and ary[left] < key:
            left += 1
        if left < right:
            ary[right] = ary[left]
            right -= 1
    ary[left] = key
    qsort(ary, start, left -1)
    qsort(ary, left+1, end)
    return ary


# 快速排序
def quick_sort(nums):
    if len(nums) <= 1:
        return nums

    less = []
    greater = []
    base = nums.pop()

    for x in nums:
        if x < base:
            less.append(x)
        else:
            greater.append(x)

    return quick_sort(less) + [base] + quick_sort(greater)




def quick(arr, left, right):
    def part(arr, left, right):
        temp = arr[left]
        while left < right:
            while left < right and arr[right] > temp:
                right -= 1
            arr[left] = arr[right]
            while left < right and arr[left] <= temp:
                left += 1
            arr[right] = arr[left]
        arr[left] = temp
        return left

        pass

    if left < right:
        mid = part(arr, left, right)
        quick(arr, left, mid -1)
        quick(arr, mid+1, right)



def bubble(arr):
    for i in range(len(arr)):
        flag = True
        for j in range(1, len(arr) - i):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
                flag = False
        if flag:
            break
    return arr

    mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))
